from checkers.utils import argmax, infinity

def minimax_decision(state, game):
    """Given a state in a game, calculate the best move by searching
    forward all the way to the terminal states.
    """

    player = game.to_move(state)

    def max_value(state):
        if game.terminal_test(state):
            return game.utility(state, player)
        v = -infinity
        for (a, s) in game.successors(state):
            v = max(v, min_value(s))
        return v

    def min_value(state):
        if game.terminal_test(state):
            return game.utility(state, player)
        v = infinity
        for (a, s) in game.successors(state):
            v = min(v, max_value(s))
        return v

    action, state = argmax(game.successors(state),
                           lambda ((a, s)): min_value(s))
    return action

def alphabeta_full_search(state, game, alpha=-infinity, beta=infinity):
    """Search game to determine best action; use alpha-beta pruning.
    This version searches all the way to the leaves.
    """

    player = game.to_move(state)

    def max_value(state, alpha, beta):
        if game.terminal_test(state):
            return game.utility(state, player)
        v = -infinity
        for (a, s) in game.successors(state):
            v = max(v, min_value(s, alpha, beta))
            if v >= beta:
                return v
            alpha = max(alpha, v)
        return v

    def min_value(state, alpha, beta):
        if game.terminal_test(state):
            return game.utility(state, player)
        v = infinity
        for (a, s) in game.successors(state):
            v = min(v, max_value(s, alpha, beta))
            if v <= alpha:
                return v
            beta = min(beta, v)
        return v

    search = lambda ((a, s)): min_value(s, alpha, beta)
    action, state = argmax(game.successors(state), search)
    return action

def alphabeta_search(state, game, d=4, cutoff_test=None,
                     eval_fn=None, alpha=-infinity, beta=-infinity):
    """Search game to determine best action; use alpha-beta pruning.
    This version cuts off search and uses an evaluation function.
    """

    player = game.to_move(state)

    def max_value(state, alpha, beta, depth):
        if cutoff_test(state, depth):
            return eval_fn(state)
        v = -infinity
        for (a, s) in game.successors(state):
            v = max(v, min_value(s, alpha, beta, depth+1))
            if v >= beta:
                return v
            alpha = max(alpha, v)
        return v

    def min_value(state, alpha, beta, depth):
        if cutoff_test(state, depth):
            return eval_fn(state)
        v = infinity
        for (a, s) in game.successors(state):
            v = min(v, max_value(s, alpha, beta, depth+1))
            if v <= alpha:
                return v
            beta = min(beta, v)
        return v

    # The default test cuts off at depth d or at a terminal state
    default_cutoff = lambda state, depth: (depth > d or
                                           game.terminal_test(state))
    cutoff_test = (cutoff_test or default_cutoff)
    eval_fn = eval_fn or (lambda state: game.utility(state, player))
    search = lambda ((a, s)): min_value(s, alpha, beta, 0)
    action, state = argmax(game.successors(state), search)
    return action
